Năm 1952-1954, Bohdan Stashynsky dự học khóa đào tạo chuyên sâu tình báo ở Kiev, học tiếng Đức và tiếng Ba Lan. Sau đó, ông làm việc ở Ba Lan và CHDC Đức với tên Joseph Lehmann, phục vụ ở Văn phòng đại diện của Liên Xô tại chính phủ của CHDC Đức, và phiên dịch tại Bộ Nội vụ và Ngoại thương.

Từ năm 1956 với danh tính giả Lehmann ông thường tới München. Sau đó nhận lệnh trực tiếp từ trụ sở KGB ở Moskva ông thực hiện tại München tháng 10/1957 vụ ám sát Lev Rebet lãnh đạo Tổ chức Quốc dân Ukraina (tiếng Ukraina: Організація Українських Націоналістів hay ОУН, chữ Latin: OUN). Phương tiện ám sát là súng phun bắn một luồng khí độc từ viên nang xyanua nghiền nát, loại chất độc gây ngừng tim, khiến cái chết của nạn nhân trông giống như một cơn đau tim, và được coi là có nguyên nhân tự nhiên.

Tại CHDC Đức Bohdan gặp cô thợ làm tóc Inge Pohl. Lúc đầu KGB đã cố gắng thuyết phục ông không kết hôn với người nước ngoài, nhưng ông ta vẫn kiên trì. Về sau với thành tích công tác của ông, năm 1957 KGB đã đồng ý, Inge Pohl trở thành vợ ông, với yêu cầu trở thành công dân Liên Xô và đến sống ở Moskva.

Tháng 10/1959 với tên giả Hans Joachim Budeit, mật danh gián điệp Taras (tiếng Ukraina: Тарас), và phiên bản cải tiến của khẩu súng bắn khí xyanua, ông ám sát Stepan Bandera lúc trưa ở cửa nhà riêng của ông này. Stashynsky biến mất nhanh chóng, nhưng lần này chất độc không bay hơi đủ nhanh, và thực tế vụ giết người đã được ghi nhận thông qua chất độc [1]. Năm đó ông đã được Nhà nước Liên Xô trao tặng Huân chương Cờ đỏ. Người khởi xướng vụ sát hại Stepan Bandera là Alexey Kirichenko (Алексей Илларионович Кириченко), ủy viên Ban Bí thư Trung ương Đảng Cộng sản Liên Xô [3].

Hoạt động của Stashinsky ở KGB và vụ ám sát Stepan Bandera đã làm nền cho cuốn tiểu thuyết của nhà văn Hà Lan Rogier van Aerde "Nỗ lực".